package test;

import org.junit.Test;
import util.GsonUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by yzy on 2020-02-11 20:21
 */
public class OnlineJudge1 {

    @Test
    public void test01(){
        Tree n1 = Tree.getInstance(Tree.geLeaf(7), Tree.geLeaf(2), 11);
        Tree n2 = Tree.getInstance(Tree.geLeaf(5), Tree.geLeaf(1), 4);

        Tree leChild = Tree.geLeftChild(n1, 4);
        Tree riChild = Tree.getInstance(Tree.geLeaf(13), n2, 8);
        Tree root = Tree.getInstance(leChild, riChild, 5);

        List<List<Integer>> lists = solve2(root, 22);
        System.out.println(GsonUtil.toJson(lists));


        TimeSplit t1 = TimeSplit.getIns(1,4);
        TimeSplit t2 = TimeSplit.getIns(2,5);
        TimeSplit t3 = TimeSplit.getIns(8,9);

        List<TimeSplit> list = new ArrayList<>(3);
        list.add(t1);
        list.add(t2);
        list.add(t3);

        List<TimeSplit> timeSplits = solve1(list);
        System.out.println(GsonUtil.toJson(timeSplits));

    }



    public static List<TimeSplit> solve1(List<TimeSplit> timeList){
        int minStart = timeList.get(0).start;
        int maxEnd = timeList.get(0).end;

        List<TimeSplit> result = new ArrayList<>();
        result.add(timeList.get(0));

        for(int i=1; i<timeList.size(); i++){
            TimeSplit curr = timeList.get(i);
            int currStart = curr.start;
            int currEnd = curr.end;

            if(currStart > maxEnd){
                maxEnd = currEnd;
                result.add(curr);
                continue;
            }
            if(currEnd < minStart){
                minStart = currStart;
                result.add(curr);
                continue;
            }

            int startInTimeIdx = -1;
            int endInTimeIdx = -1;
            for(int j=0; j<result.size(); j++){
                if(startInTimeIdx != -1 && endInTimeIdx != -1){
                    break;
                }
                startInTimeIdx = result.get(j).inTime(currStart) ? j : startInTimeIdx;
                endInTimeIdx = result.get(j).inTime(currEnd) ? j : endInTimeIdx;
            }

            int nodeStart = currStart;
            int nodeEnd = currEnd;
            if(startInTimeIdx != -1){
                nodeStart = result.get(startInTimeIdx).start;
                result.remove(startInTimeIdx);
            }
            if(endInTimeIdx != -1){
                nodeEnd = result.get(endInTimeIdx).end;
                result.remove(endInTimeIdx);
            }
            TimeSplit newNode = new TimeSplit();
            newNode.start = nodeStart;
            newNode.end = nodeEnd;
            result.add(newNode);
        }

        return result;
    }


    public static class TimeSplit{
        int start;
        int end;

        public static TimeSplit getIns(int start, int end){
            TimeSplit t = new TimeSplit();
            t.start=start;
            t.end = end;
            return t;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public boolean inTime(int t){
            return t>start && t<end;
        }

        @Override
        public String toString() {
            return "TimeSplit{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }



    public static List<List<Integer>> solve2(Tree root, int target){
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tmpList = new ArrayList<>();
        DFS(result, tmpList, root, target);
        return result;
    }

    public static void DFS(List<List<Integer>> result, List<Integer> tmpList, Tree currNode, int target){
        if(currNode == null){
            return;
        }

        int currVal = currNode.val;
        target = target - currVal;
        if(target < 0){
            return;
        }


        tmpList.add(currVal);
        if(target==0 && currNode.left==null && currNode.right==null){
            result.add(new ArrayList<>(tmpList));
            tmpList.remove(tmpList.size()-1);
            return;
        }

        DFS(result, tmpList, currNode.left, target);
        DFS(result, tmpList, currNode.right, target);
        tmpList.remove(tmpList.size()-1);

    }


    static class Tree{
        Tree left;
        Tree right;
        int val;

        public static Tree getInstance(Tree left, Tree right, int val) {
            Tree curr = new Tree();
            curr.left = left;
            curr.right = right;
            curr.val = val;
            return curr;
        }

        public static Tree geLeaf(int val) {
            Tree curr = new Tree();
            curr.val = val;
            return curr;
        }

        public static Tree geLeftChild(Tree left, int val) {
            Tree curr = new Tree();
            curr.val = val;
            curr.left = left;
            return curr;
        }




        public Tree getLeft() {
            return left;
        }

        public void setLeft(Tree left) {
            this.left = left;
        }

        public Tree getRight() {
            return right;
        }

        public void setRight(Tree right) {
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }
    }

}



